//========================================================================
/**
*  Copyright (c), 2007-2009.
*  @file	cx_list.h
*  @author	godwinguo
*  @email	godwinguo@tencent.com
*  @brief	Red-black search tree
*  @version	1.0.0
*  @history
*    <author>      <time>      <version>     <desc>
*  ------------ ------------  ------------  -----------------
*    godwinguo   2010/01/19     1.0.0        Create
*/
//========================================================================

#ifndef __CX_RBTREE_H__
#define __CX_RBTREE_H__

#include "cx_platforms.h"
#include "cx_typedef.h"
//#include "cx_platform_base.h"

#if defined(_MSVC)
#pragma once
#pragma warning(disable: 4251)
#endif	// #if defined(_MSVC)

/*************************************************************************
* MACRO
*************************************************************************/

#define RB_RED		0
#define RB_BLACK	1

#if defined(__CC_ARM)
#define __ALIGN( __x )	__align(4)
#else	// #if defined(__CC_ARM)
#define __ALIGN( __x )
#endif	// #if defined(__CC_ARM)

#define __FAR_PROC	*

/*************************************************************************
* TYPE
*************************************************************************/

typedef signed long ( __FAR_PROC cx_i2_fptr_t )( void * v0, void * v1 );

/*************************************************************************
* PROTOTYPE
*************************************************************************/

struct __struct_rb_node;
typedef struct __struct_rb_node		rb_node_t;
typedef struct __struct_rb_node *	rb_node_ptr_t;

/*************************************************************************
* STRUCTURE
*************************************************************************/

__ALIGN(4) struct __struct_rb_node
{
	unsigned long	color;
	
	rb_node_ptr_t	parent;
	rb_node_ptr_t	left;
	rb_node_ptr_t	right;

	unsigned long	key;
	unsigned long	val;
};

/*************************************************************************
* EXPORTED FUNCTION
*************************************************************************/

#if defined(__cplusplus)
extern "C" {
#endif	// #if defined(__cplusplus)

rb_node_ptr_t		cx_rb_allocNode( void );
void				cx_rb_freeNode( rb_node_ptr_t node );

rb_node_ptr_t		cx_rb_insert( rb_node_ptr_t root, rb_node_ptr_t node );
rb_node_ptr_t		cx_rb_erase( rb_node_ptr_t root, rb_node_ptr_t node );
rb_node_ptr_t		cx_rb_search( rb_node_ptr_t root, cx_i2_fptr_t cmp_func, void * key,
									rb_node_ptr_t * parent, rb_node_ptr_t ** pplink );
rb_node_ptr_t		cx_rb_replace( rb_node_ptr_t root, rb_node_ptr_t old_node, rb_node_ptr_t new_node );

rb_node_ptr_t		cx_rb_next( rb_node_ptr_t node );
rb_node_ptr_t		cx_rb_prev( rb_node_ptr_t node );
rb_node_ptr_t		cx_rb_first( rb_node_ptr_t root );
rb_node_ptr_t		cx_rb_last( rb_node_ptr_t root );

#if defined(__cplusplus)
};
#endif	// #if defined(__cplusplus)

#endif	// #ifndef __CX_RBTREE_H__


